package baodian;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static common.Util.swap;

/**
 * @author fance
 * @date 18-4-15 上午6:50
 */
public class Sort {

    void insertSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int tmp = a[i];
            int j = i;
            for (; j > 0 && a[j - 1] > tmp ; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    void insertSortAgain(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int tmp = a[i];
            int j = i;
            for (;j > 0 && a[j - 1] > tmp;j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    void shellSort(int[] a, int n) {
        for (int increment = n / 2; increment > 0 ; increment /= 2) {
            for (int i = increment; i < n; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= increment; j -= increment) {
                    if (tmp < a[j - increment]) {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }
                }
                a[j] = tmp;
            }
        }
    }

    void shellSortAgain(int[] a, int n) {
        for (int increment = n / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < n; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= increment ; j -= increment) {
                    if (tmp < a[j - increment]) {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }
                }
                a[j] = tmp;
            }
        }
    }
    void selectSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int small = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[small]) {
                    small = j;
                }
            }
            if (small != i) {
                swap(a, i, small);
            }

        }
    }

    void bubbleSortI(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if (a[j] > a[j + 1]){
                    swap(a, j, j + 1);
                }
            }
        }
    }
    void bubbleSortII(int[] a, int n) {
        boolean flag = true;
        for (int i = 1; i < n && flag; i++) {
            flag = false;
            for (int j = 0; j < n - i; j++) {
                if (a[j] > a[j + 1]){
                    flag = true;
                    swap(a, j, j + 1);
                }
            }
        }
    }

    static int[] tmp;
    void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = tmp[j++];
            } else if (j > hi) {
                a[k] = tmp[i++];
            } else if (tmp[i] < tmp[j]) {
                a[k] = tmp[i++];
            } else {
                a[k] = tmp[j++];
            }
        }
    }
    void mergeSort(int[] a, int n) {
        tmp = new int[n];
        mergeSort(a, 0, n - 1);
    }
    void mergeSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    void quickSort(int[] a, int n) {
        quickSort(a, 0, n - 1);
    }
    void quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }
    public static int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

    int leftChild(int i) {
        return 2 * i + 1;
    }
    void sink(int[] a, int i, int n) {
        int child;
        int tmp = a[i];
        for (; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child + 1] > a[child]) {
                child++;
            }
            if (tmp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;
    }
    void heapSort(int[] a, int n) {
        for (int i = n / 2; i >= 0; i--) {
            sink(a, i, n); // build
        }
        for (int i = n - 1; i > 0; i--) {
            swap(a, 0, i);// delMax
            sink(a, 0, i);
        }
    }

    void cntSort(int[] a, int n) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        int[] cnt = new int[max + 1];
        for (int i = 0; i < n; i++) {
            cnt[a[i]]++;
        }
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            while (cnt[i] != 0) {
                a[index++] = i;
                cnt[i]--;
            }
        }
    }

    void radixSort(int[] a, int n) {
        int max = a[0];
        for (int i = 1; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }

        int time = 0;
        while (max > 0) {
            max /= 10;
            time++;
        }

        List<List<Integer>> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            List<Integer> q = new ArrayList<>();
            queue.add(q);
        }

        for (int i = 0; i < time; i++) {
            for (int j = 0; j < n; j++) {
                int x = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                List<Integer> queue2 = queue.get(x);
                queue2.add(a[j]);
                queue.set(x, queue2);
            }

            int cnt = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    List<Integer> queue3 = queue.get(k);
                    a[cnt] = queue3.get(0);
                    queue3.remove(0);
                    cnt++;
                }
            }

        }

        }


    @Test
    public void test() {
        /*Random random = new Random(47);
        int[] a = new int[1000];
        for (int i = 0; i < 1000; i++) {
            a[i] = random.nextInt();
        }*/
        int[] a = {10,23,33,9,101};
        long st = System.currentTimeMillis();
        // 225 selectSort(a, a.length);
          shellSort(a, a.length);
//         191 bubbleSort(a, a.length);
//          bubbleSortI(a, a.length);
//          bubbleSortII(a, a.length);
//         insertSort(a, a.length);
        // 7 heapSort(a, a.length);
//          mergeSort(a, a.length);
        // 4 quickSort(a, a.length);
        // oom ... cntSort(a, a.length); 适用与数字不大的情况
//         ArrayIndexOutOfBoundsException ... radixSort(a, a.length);
//        radixSort(a, a.length);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        System.out.println(System.currentTimeMillis() - st);

    }
}
